package com.ma.dp.a01;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @ClassName Solution514
 * @Author: mayongqiang
 * @DATE 2022/4/15 10:35
 * @Description:
 */
public class Solution514 {

    // 存储ring中不同字母的索引集合
    Map<Character, List<Integer>> charToIndex = new HashMap<>();
    // 备忘录
    int[][] memo;

    public int findRotateSteps(String ring, String key) {
        int m = ring.length(), n = key.length();
        memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            char c = ring.charAt(i);
            if (!charToIndex.containsKey(c)) {
                charToIndex.put(c, new LinkedList<>());
            }
            charToIndex.get(c).add(i);
        }
        // dp[i][j] = x 表示指针指向i时，拼好key[j...]的最少步数为x  我们需要的最终结果即为dp[0][0]
        return dp(ring, 0, key, 0);
    }

    // 带备忘录的递归解决
    int dp(String ring, int i, String key, int j) {
        int n = ring.length();
        // base case j=0时无需匹配，步数为0
        if (j == key.length()) {
            return 0;
        }
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        //求最小,设置哨兵
        int res = Integer.MAX_VALUE;
        //现在需要将指针 由i拨向key[j] 首先在ring中找key[j]
        for (int k : charToIndex.get(key.charAt(j))) {
            int delta = Math.abs(i - k);
            delta = Math.min(delta, n - delta);
            res = Math.min(res, 1 + delta + dp(ring, k, key, j + 1));
        }
        memo[i][j] = res;
        return res;

    }

}
